package com.sheng.leetcode.year2023.month05.day30;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2023/05/30
 * <p>
 * 1110. 删点成林<p>
 * <p>
 * 给出二叉树的根节点 root，树上每个节点都有一个不同的值。<p>
 * 如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。<p>
 * 返回森林中的每棵树。你可以按任意顺序组织答案。<p>
 * <p>
 * 示例 1：<p>
 * 输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]<p>
 * 输出：[[1,2,null,4],[6],[7]]<p>
 * <p>
 * 示例 2：<p>
 * 输入：root = [1,2,4,null,3], to_delete = [3]<p>
 * 输出：[[1,2,4]]<p>
 * <p>
 * 提示：<p>
 * 树中的节点数最大为 1000。<p>
 * 每个节点都有一个介于 1 到 1000 之间的值，且各不相同。<p>
 * to_delete.length <= 1000<p>
 * to_delete 包含一些从 1 到 1000、各不相同的值。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/delete-nodes-and-return-forest">1110. 删点成林</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1110 {

    @Test
    public void test01() {
        TreeNode left = new TreeNode(2);
        left.left = new TreeNode(4);
        left.right = new TreeNode(5);
        TreeNode right = new TreeNode(3);
        right.left = new TreeNode(6);
        right.right = new TreeNode(7);
        TreeNode root = new TreeNode(1);
        root.left = left;
        root.right = right;
        int[] to_delete = {3, 5};
        List<TreeNode> treeNodes = new Solution().delNodes(root, to_delete);
        System.out.println(treeNodes);
    }
}

class Solution {

    List<TreeNode> nodes = new ArrayList<>();

    int[] to;

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        to = to_delete;
        root = dfs(root, false);
        return nodes;
    }

    public TreeNode dfs(TreeNode root, boolean b) {
        boolean flag = true;
        for (int i : to) {
            if (i == root.val) {
                flag = false;
                break;
            }
        }
        if (flag && !b) {
            nodes.add(root);
        }
        if (root.left != null) {
            root.left = dfs(root.left, flag);
        }
        if (root.right != null) {
            root.right = dfs(root.right, flag);
        }
        return flag ? root : null;
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
